package com.czk.tree;

/**
 * 数组存储二叉树
 * 堆排序的应用
 * @Author:ChenZhangKun
 * @Date: 2020/7/7 20:43
 */
public class ArrayBinaryTreeDemo {
    public static void main(String[] args) {
        ArrayBinaryTree arrayBinaryTree=new ArrayBinaryTree(new int[]{1,2,3,4,5,6,7});
        // 前序遍历
        arrayBinaryTree.preTraverse();
        System.out.println();
        // 中序遍历
        arrayBinaryTree.inOrderTraverse();
        System.out.println();
        // 后续遍历
        arrayBinaryTree.postTraverse();

    }
}
class ArrayBinaryTree{
    // 存储数据节点的数组
    private int[] array;

    public ArrayBinaryTree(int[] array) {
        this.array = array;
    }
    // 重载方法
    public void preTraverse(){
        this.preTraverse(0);
    }
    // 编写方法完成顺序存储二叉树的前序遍历
    // index是数组的下标
    public void preTraverse(int index){
        // 如果数组为空，或者index大于索引，或者数组长度等于0
        if (array==null||array.length==0){
            System.out.println("数组为空");
            return;
        }
        // 输出当前数组的前序遍历
        System.out.print(array[index]+"  " );
        // 向左递归
        if ((index*2+1)<array.length){
            preTraverse((index*2)+1);
        }
        if ((index*2+2)<array.length){
            preTraverse((index*2)+2);
        }
    }
    // 中序重载方法
    public void inOrderTraverse(){
        this.inOrderTraverse(0);
    }
    // 编写方法完成顺序存储二叉树的中序遍历
    // index是数组的下标
    public void inOrderTraverse(int index){
        // 如果数组为空，或者index大于索引，或者数组长度等于0
        if (array==null||array.length==0){
            System.out.println("数组为空");
            return;
        }
        // 向左递归
        if ((index*2+1)<array.length){
            preTraverse((index*2)+1);
        }
        // 输出当前数组的前序遍历
        System.out.print(array[index]+"  " );
        if ((index*2+2)<array.length){
            preTraverse((index*2)+2);
        }
    }
    // 后序重载方法
    public void postTraverse(){
        this.postTraverse(0);
    }
    // 编写方法完成顺序存储二叉树的后续遍历
    // index是数组的下标
    public void postTraverse(int index){
        // 如果数组为空，或者index大于索引，或者数组长度等于0
        if (array==null||array.length==0){
            System.out.println("数组为空");
            return;
        }
        // 向左递归
        if ((index*2+1)<array.length){
            preTraverse((index*2)+1);
        }

        if ((index*2+2)<array.length){
            preTraverse((index*2)+2);
        }
        // 输出当前数组的前序遍历
        System.out.print(array[index]+"  " );
    }
}
